/**
 * 
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个
输入： amount = 5, coins = [1, 2, 5]；
输出： 4
 */

/**
 * 回溯解决 
 * 不限制层数
 * 【终止】sum == amount;
 * 【剪枝】排序coins
 * 🤔️ 元素可以重复用， 但是元素是无序的？ coins是不重复的
path [ 1, 1, 1, 1, 1 ]
path [ 1, 1, 1, 2 ]
path [ 1, 2, 2 ]
path [ 5 ]
 * 会超出时间限制
 */
var change = function (amount, coins) {
  const path = []
  coins.sort((a,b)=>a-b)
  const backTrack = (sum,index)=>{
    if(sum>=amount) {
      res.push(path.slice())
      return
    }
    for(let i=index;i<coins.length;i++) {
      if(sum+coins[i]>amount) break
      path.push(coins[i])
      backTrack(sum+coins[i], i)
      path.pop()
    }
  }
  backTrack(0,0)
  return res.length;
}
const amount = 5, coins = [1, 2, 5];
console.log('零钱兑换2', change(amount, coins)); //4
/**
无限个--完全背包
dp[j] 金额数为j的组合个数
dp[j]+=dp[j-coins[i]]
## 组合数（无顺序）：外层物品 内层容量
## 排列数（要求顺序）：外层容量 内层物品
 */
// var change = function (amount, coins) {
//   const dp = Array(amount + 1).fill(0);
//   dp[0] = 1; //递归基础
//   for (let i = 0; i < coins.length; i++) {
//     for (let j = coins[i]; j <= amount; j++) {
//       dp[j] += dp[j - coins[i]];
//     }
//   }
//   return dp[amount];
// };
// const amount = 5, coins = [1, 2, 5];
// console.log('零钱兑换2', change(amount, coins));
/**
 * review 1214✅
 */